#pragma once

#include "BianryTreeNode.h"
#include <memory>

class TreeHelper
{
public:
	template<typename T>
	static int height(std::shared_ptr<BinaryTreeNode<T>> node)
	{
		if (node)
		{
			auto leftHeight = height(node->left());
			auto rightHeight = height(node->right());

			return max(leftHeight, rightHeight) + 1;
		}
		else
		{
			return 0;
		}
	}

	template<typename T>
	static int minHeight(std::shared_ptr<BinaryTreeNode<T>> node)
	{
		if (node)
		{
			auto leftHeight = minHeight(node->left());
			auto rightHeight = minHeight(node->right());

			if (leftHeight <= rightHeight)
			{
				return leftHeight + 1;
			}
			else
			{
				return rightHeight + 1;
			}
		}

		return 0;
	}

	template<typename T>
	static std::shared_ptr<BinaryTreeNode<T>> add(std::shared_ptr<BinaryTreeNode<T>> node, T const& value)
	{
		std::shared_ptr<BinaryTreeNode<T>> ret;
		auto leftHeight = minHeight(node->left());
		auto rightHeight = minHeight(node->right());
		if (leftHeight <= rightHeight)
		{
			if (leftHeight == 0)
			{
				ret = std::make_shared<BinaryTreeNode<T>>(value);
				node->setLeft(ret);
			}
			else
			{
				ret = add(node->left(), value);
			}
		}
		else
		{
			if (rightHeight == 0)
			{
				ret = std::make_shared<BinaryTreeNode<T>>(value);
				node->setRight(ret);
			}
			else
			{
				ret = add(node->right(), value);
			}
		}

		return ret;
	}

	template<typename T>
	static bool isBalanced(std::shared_ptr<BinaryTreeNode<T>> node)
	{
		if (!node)
		{
			return true;
		}

		auto leftHeight = height(node->left());
		auto rightHeight = height(node->right());
		if (abs(leftHeight - rightHeight) <= 1)
		{
			return isBalanced(node->left()) && isBalanced(node->right());
		}
		else
		{
			return false;
		}
	}
};

